This invention relates to techniques for encoding finite state machine (FSM) data structures. More specifically, this invention relates to the storage of an FSM data structure in a compact encoded form.
U.S. Pat. Nos. 4,241,402 and 4,285,049 each relate to a finite state automaton which receives signals and, based on the received signals and on control tables, steps from a present state along a transition to a next state, eventually reaching a report state dependent on the received signal sequence. The signals may, for example, be a sequence of character elements. The control tables contain information from a finite state machine ("FSM") data structure. In general, FSM data structures include information about states and transitions between states, and the information in a specific data structure may be encoded in many ways. The encodings disclosed in U.S. Pat. Nos. 4,241,402 and 4,285,049 are conventional in that each unit of data, there called a state word, includes part of a state control table which controls the transitions from a specific state to other states. The state word may include, for example, a memory address used to obtain the address of a following state word.
It would be advantageous to have a way to encode an FSM data structure more compactly than can be achieved with the conventional techniques without sacrificing any of the information in the data structure.